package com.seven.leetcode.problems;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 781. 森林中的兔子
 * RabbitsInForest
 * https://leetcode-cn.com/problems/rabbits-in-forest/
 * 级别：Medium
 * <p>
 * 森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。
 * <p>
 * 返回森林中兔子的最少数量。
 * <p>
 * 示例:
 * 输入: answers = [1, 1, 2]
 * 输出: 5
 * 解释:
 * 两只回答了 "1" 的兔子可能有相同的颜色，设为红色。
 * 之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
 * 设回答了 "2" 的兔子为蓝色。
 * 此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
 * 因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。
 * <p>
 * 输入: answers = [10, 10, 10]
 * 输出: 11
 * <p>
 * 输入: answers = []
 * 输出: 0
 * <p>
 * 输入: answers = [1,0,1,0,0]
 * 输出: 5
 * <p>
 * 输入: answers = [0,0,1,1,1]
 * 输出: 6
 *
 * @author : wenguang
 * @date : 2021/4/02 10:42
 */
public class RabbitsInForest {

    public static void main(String[] args) {
        int[] answers = new int[]{10, 10, 10};
        System.out.println("in: \nanswers:" + Arrays.toString(answers));
        int result = numRabbits(answers);
        System.out.println("out: " + result);
    }

    public static int numRabbits(int[] answers) {
        if (null == answers || 0 == answers.length) {
            return 0;
        }

        Map<Integer, Integer> map = new HashMap<>();
        for (Integer ans : answers) {
            map.put(ans, map.getOrDefault(ans, 0) + 1);
        }

        int res = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int key = entry.getKey();
            int value = entry.getValue();
            int colorNum = (int) Math.ceil(value / (key + 1.0));
            res += colorNum * (key + 1);
        }

        return res;
    }
}
